﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Harmonogramowanie
{
    public class CGraph
    {
        public int n=0; //number of nodes
        List<int>[] _Succ; //lists of succesors
        List<int>[] _Pred; //lists of predecessors
        public int[] Weights; //Weights of nodes
        public int[] Res; // assign to resource 

        //create empty lists for graph with n nodes
        public void Init(int pn)
        {
            n = pn;
            Res = new int[n + 1];
            Weights = new int[n + 1];
            _Succ = new List<int>[n + 1];
            _Pred = new List<int>[n + 1];
            for (int i = 0; i <= n; i++)
            { _Succ[i] = new List<int>(); _Pred[i] = new List<int>(); }
        }

        // add arc linked node f with node t
        public void addarc(int f, int t)
        { _Succ[f].Add(t); _Pred[t].Add(f); }

        //return list of succesors of node "node"
        public List<int> Succ(int node) { return _Succ[node]; }

        //return list of predecessors of node "node"
        public List<int> Pred(int node) { return _Pred[node]; }


        static public int[] TopOrder(CGraph G)
        {
            int[] LP = new int[G.n + 1];
            int[] ORD = new int[G.n + 1];

            for (int i = 1; i <= G.n; i++) LP[i] = G.Pred(i).Count;
            Queue<int> Q = new Queue<int>();
            for (int i = 1; i <= G.n; i++) if (LP[i] == 0) Q.Enqueue(i);
            int l = 0;
            while (Q.Count > 0)
            {
                int w = Q.Dequeue();
                ORD[++l] = w;
                foreach (int ns in G.Succ(w))
                    if (--LP[ns] == 0) Q.Enqueue(ns);
            }
            if (l < G.n) ORD[0] = -1; else ORD[0] = 0;
            return ORD;
        }


        static public int HARM(CGraph G, int[] TopOrder, int[] S, int[] C, int[] PH)
        {
            for (int i = 1; i <= G.n; i++) PH[i] = 0;
            for (int i = 1; i <= G.n; i++)
            {
                int w = TopOrder[i], s = 0;
                foreach (int p in G.Pred(w))
                    if (s < C[p]) { s = C[p]; PH[w] = p; }
                S[w] = s; C[w] = s + G.Weights[w];
            }
            PH[0] = 1; for (int i = 1; i <= G.n; i++)
                if (C[PH[0]] < C[i]) PH[0] = i; ;
            return C[PH[0]];
        }






    
    }
}
